public class MyLeetCode {
    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    //返回链表相交的结点
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA == headB){
                return headA;
            }
            ListNode cur = headA;
            ListNode cur1 = headB;
            if(size(headA)-size(headB)>0){
                int step = size(headA)-size(headB);
                while(step > 0){
                    cur =cur.next;
                    step--;
                }
                while(cur!=null){
                    if(cur != cur1){
                        cur = cur.next;
                        cur1 = cur1.next;
                    }else{
                        return cur;
                    }
                }
            }else{
                int step = size(headB)-size(headA);
                while(step > 0){
                    cur1 = cur1.next;
                    step--;
                }
                while(cur!=null){
                    if(cur!=cur1 ){
                        cur = cur.next;
                        cur1 = cur1.next;
                    }else{
                        return cur;
                    }
                }
            }
            return null;
        }
        private int size(ListNode head){
            if(head == null){
                return 0;
            }
            int count = 0;
            ListNode cur = head;
            while(cur!=null){
                cur = cur.next;
                count++;
            }
            return count;
        }
        // 判断链表带环
            public boolean hasCycle(ListNode head) {
                ListNode fast = head;
                ListNode slow = head;
                while(fast!=null&&fast.next!=null){
                    slow = slow.next;
                    fast = fast.next.next;
                    if(slow == fast){
                        return true;
                    }
                }
                return false;
            }
            //返回链表相交的位置
        public ListNode detectCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    break;
                }

            }
            if(fast == null|| fast.next == null){
                return null;
            }
            slow = head;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;

        }

    }
}
